package leetcode.数学;

/**
 * 两数相除
 */
public class Test29两数相除 {
    /**
     *
     * 任何一个整数可以表示成以2的幂为底的一组基的线性组合,就是把十进制转二进制的过程。比如：9=2^3 + 2^0
     * <p>
     * 左移一位相当于乘以2,右移一位相当于除以2.（这里不考虑溢出啥的）
     * <p>
     * 基于以上常识，解法如下：
     * 先让除数一直左移，直到大于被除数之前得到一个最大的基数。
     * 然后接下来我们每次尝试减去这个基，如果可以则结果增加2^k,然后基继续右移迭代，直到基为0为止。
     * 因为这个方法的迭代次数是按2的幂知道超过结果，所以时间复杂度为O(log(n))。
     */
    public int divide(int dividend, int divisor) {// 被除数  除数
        // 溢出处理
        if (divisor == 0 || (dividend == Integer.MIN_VALUE && divisor == -1)) {
            return Integer.MAX_VALUE;
        }
        // 求结果的符号
        int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
        // 求绝对值，为防止溢出使用long
        long dvd = Math.abs((long) dividend);
        long dvs = Math.abs((long) divisor);
        // 记录结果
        int result = 0;

        // 被除数大于除数
        while (dvd >= dvs) {
            // 记录除数
            long tmp = dvs;
            // 记录商的大小
            long mul = 1;
            while (dvd >= (tmp << 1)) {
                tmp <<= 1;
                mul <<= 1;
            }
            // 减去最接近dvd的dvs的指数倍的值（值为tmp）
            dvd -= tmp;
            // 修正结果
            result += mul;
        }
        return result * sign;
    }

    public static void main(String[] args) {
        // 5 * 3
        int sum = 0;
        for (int i = 0; i < 3; i++) {

        }
        System.out.println();

    }
}
